import heapq


class MedianFinder:

    def __init__(self):
        self.val = None
        self.leftNum = 0
        self.rightNum = 0
        self.leftHeap = []
        self.rightHeap = []
        self.dic = {}

    def addNum(self, num: int) -> None:
        if self.val is None:
            self.val = num
            self.dic[num] = 1
            return

        if self.val == num:
            self.dic[num] += 1
        elif self.val > num:
            if num in self.dic:
                self.dic[num] += 1
            else:
                self.dic[num] = 1
                heapq.heappush(self.leftHeap, num * (-1))
            self.leftNum += 1
        else:
            if num in self.dic:
                self.dic[num] += 1
            else:
                self.dic[num] = 1
                heapq.heappush(self.rightHeap, num)
            self.rightNum += 1

        # 调整
        if self.dic[self.val] <= abs(self.rightNum - self.leftNum):
            if self.dic[self.val] == abs(self.rightNum - self.leftNum):
                if self.leftNum > self.rightNum:
                    tmpVal = self.val
                    self.val = heapq.heappop(self.leftHeap) * (-1)
                    heapq.heappush(self.rightHeap, tmpVal)
                    self.rightNum += self.dic[tmpVal]
                    self.leftNum -= self.dic[self.val]
            else:
                if self.leftNum > self.rightNum:
                    tmpVal = self.val
                    self.val = heapq.heappop(self.leftHeap) * (-1)
                    heapq.heappush(self.rightHeap, tmpVal)
                    self.rightNum += self.dic[tmpVal]
                    self.leftNum -= self.dic[self.val]
                else:
                    tmpVal = self.val
                    self.val = heapq.heappop(self.rightHeap)
                    heapq.heappush(self.leftHeap, tmpVal * (-1))
                    self.rightNum -= self.dic[self.val]
                    self.leftNum += self.dic[tmpVal]

    def findMedian(self) -> float:
        if (self.rightNum + self.leftNum + self.dic[self.val]) % 2 != 0 or self.dic[self.val] > abs(
                self.rightNum - self.leftNum):
            return self.val
        if self.leftNum > self.rightNum:
            return (self.val + self.leftHeap[0] * (-1)) / 2
        else:
            return (self.val + self.rightHeap[0]) / 2


if __name__ == '__main__':
    obj = MedianFinder()
    obj.addNum(-1)
    r = obj.findMedian()
    print(r)
    obj.addNum(-2)
    r = obj.findMedian()
    print(r)
    obj.addNum(-3)
    r = obj.findMedian()
    print(r)
    obj.addNum(-4)
    r = obj.findMedian()
    print(r)
    obj.addNum(-5)
    r = obj.findMedian()
    print(r)
